package com.xzz.treeBST;

/**
 * @author: hhz
 * @create: 2021-12-21 11:13
 * 450. 删除二叉搜索树中的节点
 * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 *
 * 一般来说，删除节点可分为两个步骤：
 *
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 *
 **/
public class DeleteNode {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        print(node1);
        System.out.println();
        TreeNode treeNode = deleteNode(node1, 3);
        print(treeNode);
    }
    public static TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if(root.val ==key){
            //1.找到目标节点 该节点的左右子节点都为null,该节点直接去世
            //2.找到目标节点 该节点的左子节点为null,返回该节点右子节点
            //3.找到目标节点 该节点的右子节点为null,返回该节点左子节点
            if(root.left==null){
                return root.right;
            }
            if(root.right==null){
                return root.left;
            }
            //4.找到目标节点 该节点的左右子节点都不为null
//            //4.1取右子树的最小节点代替当前节点
//            TreeNode min = getMin(root.right);
//            // 删除右子树最小的节点
//            root.right = deleteNode(root.right,min.val);
//            min.left = root.left;
//            min.right = root.right;
//            root = min;

            //4.1取左子树的最大节点代替当前节点
            TreeNode max = getMax(root.left);
            // 删除右子树最小的节点
            root.left = deleteNode(root.left,max.val);
            max.left = root.left;
            max.right = root.right;
            root = max;
        }
        if(root.val>key){
            root.left = deleteNode(root.left,key);
        }
        if(root.val<key){
            root.right = deleteNode(root.right,key);
        }
        return root;
    }

    //获取最小的
    public static TreeNode getMin(TreeNode root) {
        while(root.left!=null){
            root = root.left;
        }
        return root;
    }
    //获取最大的
    public static TreeNode getMax(TreeNode root) {
        while(root.right!=null){
            root = root.right;
        }
        return root;
    }
    public static void print(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + ",");
            print(root.left);
            print(root.right);
        }
    }
}
